#include <iostream>
#include <cstring>
#include <queue>

struct state { int x, y, dir, dis; bool gold; };

int const maxn = 22;
bool vis[maxn][maxn][4][2];
int da[maxn][maxn];
int n;

int const opt[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

bool inrange(int x, int y)
{
	return (0 <= x && x < n) && (0 <= y && y < n);
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T;
	std::cin >> T;
	while (T--) {
		std::cin >> n;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) da[i][j] = 0;
		std::memset(vis, 0, sizeof(vis));

		int id, x, y;
		while (std::cin >> id >> x >> y && id != -1) da[x][y] = id;

		if (da[0][0] == 2 || da[0][0] == 1) { std::cout << "-1\n"; continue; }
		if (da[0][0] == 3) { std::cout << "980\n"; continue; }

		// dir right: 0   up: 1   left: 2   down: 3
		std::queue<state> q;
		vis[0][0][0][0] = true;
		q.push({0, 0, 0, 0, false});
		bool can = false;
		int min_step;
		while (!q.empty()) {
			state now = q.front(); q.pop();
			if (!now.x && !now.y && now.gold) {
				can = true; min_step = now.dis + 1; break;
			}

			int px = now.x + opt[now.dir][0], py = now.y + opt[now.dir][1];
			if (inrange(px, py) && (!da[px][py] || da[px][py] == 3) &&
					!vis[px][py][now.dir][now.gold]) {
				state tmp = now;
				tmp.dis = now.dis + 1; tmp.x = px; tmp.y = py;
				vis[px][py][now.dir][now.gold] = true;
				q.push(tmp);
			}

			if (!vis[now.x][now.y][(now.dir + 1) % 4][now.gold]) {
				state tmp = now;
				tmp.dis = now.dis + 1; tmp.dir = (now.dir + 1) % 4;
				vis[now.x][now.y][tmp.dir][now.gold] = true;
				q.push(tmp);
			}

			if (!vis[now.x][now.y][(now.dir + 3) % 4][now.gold]) {
				state tmp = now;
				tmp.dis = now.dis + 1; tmp.dir = (now.dir + 3) % 4;
				vis[now.x][now.y][tmp.dir][now.gold] = true;
				q.push(tmp);
			}

			if (da[now.x][now.y] == 3 && !now.gold && !vis[now.x][now.y][now.dir][1]) {
				state tmp = now;
				tmp.gold = true; tmp.dis = now.dis + 1;
				vis[now.x][now.y][tmp.dir][1] = true;
				q.push(tmp);
			}
		}
		if (!can) {
			std::cout << "-1\n";
		} else {
			std::cout << 1000 - min_step * 10 << '\n';
		}
	}
}

